【题解】 Willem, Chtholly and Seniorious 珂朵莉树 luoguCF896C | Qiuly's blog!

【题解】 Willem, Chtholly and Seniorious 珂朵莉树 luoguCF896C

Posted on | Edited on | In | Comments:

神奇的珂朵莉树，优雅的暴力。

珂朵莉树的主要思想就是对于一段连续的值相同的区间，将其缩为一个结点，然后丢到 $set$ 里面，主要的操作有拆分区间操作…….这货很强大，码量不短但极好写，而且一般不会出什么问题，调试也很方便。

但是珂朵莉树的思想很暴力，比如说区间第 $K$ 大，珂朵莉树的做法就是直接将区间拿出来排一波序！当然，这样暴力的东西只能在随机数据的情况下食用，或者数据水的情况下，不然分分钟给你 $T$ 飞！

好吧来看看这道题的操作该怎么办：

第一个操作的话属于傻逼操作，珂朵莉树，先 $split$ 提取 $l,r$ 区间，然后直接暴力访问，加上 $x$ 即可。

第二个操作完全就是珂朵莉树的基本操作，跟上面一样，暴力访问然后直接将权值改为 $x$ 即可，更简单的方法就是删除 $l,r$ 区间，然后把权值统一为 $x$ 后再插入 $l,r$ 。

第三个操作第 $K$ 大，上面说了，直接拿出来排个序就好了，炒鸡暴力。

第四个操作……仍然是暴力，可以参考第一二个操作，注意 $longlong$ 的问题，不要爆 $long long$ 了。

对于初始的序列，我们先用题目要求的随机化函数得到序列中每一个位置的值，然后插入到 $set$ 中，这个时候第 $i$ 个元素区间是 $i,i$ 。

还有一个需要注意的地方，就是在插入完整个序列后还要在最后面插入一个边界的哨兵结点，当然哨兵结点的权值为 $0$ 。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<set>
#include<vector>
#include<cstdio>
#include<iostream>
#include<algorithm>

#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

typedef long long ll;

const int N=1e5+7;
const int inf=1e9+9;

ll seed,vmax;
inline ll rnd(){
    ll ret=seed;
    seed=(seed*7+13)%1000000007;
    return ret;
}

struct ODT{
    struct Node{
        int l,r;
        mutable	ll v;
        Node(int L,int R=-1,ll V=0):l(L),r(R),v(V) {}
        bool operator < (const Node&x) const {return l<x.l;}
    };

    std::set<Node> s;
    #define IT std::set<Node>::iterator

    inline IT split(int pos){
        IT it=s.lower_bound(Node(pos));
        if(it!=s.end()&&it->l==pos)return it;
        else --it;
        int L=it->l,R=it->r;ll V=it->v;
        s.erase(it);
        return s.insert(Node(L,pos-1,V)),s.insert(Node(pos,R,V)).first;
    }
    inline void assign(int l,int r,ll val){
        IT itr=split(r+1),itl=split(l);
        s.erase(itl,itr);
        s.insert(Node(l,r,val));
    }
    inline void add(int l,int r,ll val){
        IT itr=split(r+1),itl=split(l);
        for(;itl!=itr;++itl)itl->v+=val;	
    }
    inline ll rank(int l,int r,int k){
        std::vector<std::pair<ll,int> > hep;
        IT itr=split(r+1),itl=split(l);
        for(;itl!=itr;++itl)
            hep.push_back(std::make_pair(itl->v,itl->r-itl->l+1));
        std::sort(hep.begin(),hep.end());
        for(std::vector<std::pair<ll,int> >::iterator it=hep.begin();it!=hep.end();++it){
            k-=it->second;
            if(k<=0)return it->first;
        }
    }
    inline ll pow(ll x,ll y,ll mod){
        ll res=1ll;x%=mod;
        for(;y;y>>=1,x=x*x%mod)if(y&1)res=res*x%mod;
        return res%mod;
    }
    inline ll sum(int l,int r,int ex,int mod){
        IT itr=split(r+1),itl=split(l);
        ll res=0;
        for(;itl!=itr;++itl)
            res=(res+(ll)(itl->r-itl->l+1)*pow(itl->v,ll(ex),ll(mod)))%mod;
        return res;
    }
    inline void pre(int n){
        int a;
        for(int i=1;i<=n;++i)
            a=(rnd()%vmax)+1,s.insert(Node(i,i,a));
        s.insert(Node(n+1,n+1,0));
        return;
    }
}T;

int main(){
    int n,m;
    scanf("%d%d%lld%lld",&n,&m,&seed,&vmax);
    T.pre(n);
    for(int i=1;i<=m;++i){
        int op=(rnd()%4)+1,l=(rnd()%n)+1,r=(rnd()%n)+1,x,y;
        if(l>r)std::swap(l,r);
        if(op==3)x=(rnd()%(r-l+1))+1;
        else x=(rnd()%vmax)+1;
        if(op==4)y=(rnd()%vmax)+1;
        if(op==1)T.add(l,r,ll(x));
        else if(op==2)T.assign(l,r,ll(x));
        else if(op==3)printf("%lld\n",T.rank(l,r,x));
        else if(op==4)printf("%lld\n",T.sum(l,r,x,y));
    }	
    return 0;
}

本文标题:【题解】 Willem, Chtholly and Seniorious 珂朵莉树 luoguCF896C

文章作者:Qiuly

发布时间:2019年03月11日 - 00:00

最后更新:2019年03月29日 - 13:52

原始链接:http://qiulyblog.github.io/2019/03/11/[题解]luoguCF896C/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。